#include<stdlib.h>
#include<stdio.h>

//needs to be initialized to a reasonable value in PORNOS
void * heap_lower; //points to the first byte in the memory we want to manage
void * heap_upper; //points to the first byte not in the memory anymore

//int num_bytes = heap_upper - heap_lower; //will be done like this in PORNOS
int num_bytes = 1024*1024*2;

#define USED 1
#define FREE 0

struct segment_header {

  void * ptr_prev;
  void * ptr_next;
  int status;
  //the payload data follows after this

} start_segment;

/*
Remark: The size of this structure might be bigger than expected due to data alignment that is done by the compiler. I hope this does not lead to problems in PORN-OS
*/


void * porn_malloc(int num_bytes){

  //first fit, find the first free segment of sufficient size
  struct segment_header * search_seg = ((struct segment_header *) heap_lower);

  /*
    Remark: If we are doing pointer arithmetics, search_seg needs to
    be cased into (void *) or the compiler will screw it.
  */

  while(1){
   
    if(search_seg->status == FREE && //is segment free? 
       search_seg->ptr_next - (void *)search_seg  >= num_bytes){ //big enough?
      
      //printf("found free data segment @ %u\n", (unsigned int) search_seg);
      
      search_seg->status = USED;
      
      void * ptr_next = search_seg->ptr_next; //remember ptr_next
      search_seg->ptr_next = ((void*)search_seg) + sizeof(struct segment_header) + num_bytes;
      

      //create new header
      ((struct segment_header *) search_seg->ptr_next)->ptr_prev = search_seg;
      ((struct segment_header *) search_seg->ptr_next)->ptr_next = ptr_next;
      ((struct segment_header *) search_seg->ptr_next)->status = FREE;


      return ((void *)search_seg) + sizeof(struct segment_header);
      
    }else{

      //Are there more segments to check?
      if(search_seg->ptr_next != heap_upper){
	
	search_seg = search_seg->ptr_next;
	continue;

      }else{
	
	//printf("no segment of sufficient size was found\n");
	return NULL;
      }

    }

  }

  return NULL;
}


int porn_free(void * ptr){

  /*
    Remark: This function is a bit more complicated than porn_malloc,
    because we have to join adjacent free cells to keep as much memory
    as possible usable.
   */

  //We go through our linked list to check if we have ptr
  struct segment_header * search_seg = ((struct segment_header *) heap_lower);

  /*do not crash if someone tries to 'free' NULL*/
  if(ptr == NULL)
    return -1;

  while(1){
    
    if( ((void*)search_seg) == ptr - sizeof(struct segment_header) ){ //found segment, now free it
      
      /*
       We have to figure out if the segment is the first, last or in the middle, because:
       first segment has no previous segment
       last segment has no next segment
       single segment cannot be deleted
       */
      
      //do we only have one segment?
      if(search_seg->ptr_prev == heap_upper && search_seg->ptr_next == heap_upper){ 
	search_seg->status = FREE; //we cannot destroy this segment
	return 0;
      }
      
      //there is more than one segment but this is the first
      if(search_seg->ptr_prev == heap_upper && search_seg->ptr_next != heap_upper){ 
	
	//if the next segment is also free, we join them together
	if( ((struct segment_header *) search_seg->ptr_next)->status == FREE ){
	  
	  search_seg->status = FREE;
	  search_seg->ptr_next = ((struct segment_header *) search_seg->ptr_next)->ptr_next;
	  
	  if(((struct segment_header *) search_seg->ptr_next)->ptr_next != heap_upper)
	    ((struct segment_header *)((struct segment_header *) search_seg->ptr_next)->ptr_next)->ptr_prev = search_seg;
	  
	  //we devalidate the second header in case the ulp programmer has kept any references
	  ((struct segment_header *) search_seg)->ptr_prev = NULL;
	  ((struct segment_header *) search_seg)->ptr_next = NULL;
	  ((struct segment_header *) search_seg)->status = FREE;

	  return 0;
	  
	}else{
	  
	  //the structure of the linked list is preserved
	  search_seg->status = FREE;
	  return 0;
	  
	}
	
	return -1;

      }
      
       //is there more than one segment and this is the last
      if(search_seg->ptr_prev != heap_upper && search_seg->ptr_next == heap_upper){
	
	//if the previous segment is also free, we join them together
	if( ((struct segment_header *) search_seg->ptr_prev)->status == FREE ){
	  
	  ((struct segment_header *) search_seg->ptr_prev)->ptr_next = search_seg->ptr_next;

	  //we devalidate this header in case the ulp programmer has kept any references
	  search_seg->status = FREE;
	  search_seg->ptr_prev = NULL;
	  search_seg->ptr_next = NULL;

	  return 0;
	  
	}else{
	  
	  search_seg->status = FREE;
	  return 0;
	  
	}
	
	return -1;
	
      }

      if(search_seg->ptr_prev != heap_upper && search_seg->ptr_next != heap_upper){ //this is a segment in between
	
	//both neighbors are free
	if( ((struct segment_header *)search_seg->ptr_prev)->status == FREE && ((struct segment_header *)search_seg->ptr_next)->status == FREE ){
	
	  ((struct segment_header *)search_seg->ptr_prev)->ptr_next = search_seg->ptr_next;
	  ((struct segment_header *)search_seg->ptr_next)->ptr_prev = search_seg->ptr_prev;

	  //devalidate
	  search_seg->ptr_prev = NULL;
	  search_seg->ptr_next = NULL;
	  search_seg->status = FREE;
	  ((struct segment_header *)search_seg->ptr_next)->ptr_prev == NULL;
	  ((struct segment_header *)search_seg->ptr_next)->ptr_next == NULL;
	  ((struct segment_header *)search_seg->ptr_next)->status == FREE;

	  return 0;
	  
	
	}
	
	//only prev neighbor is free
	if( ((struct segment_header *)search_seg->ptr_prev)->status == FREE && ((struct segment_header *)search_seg->ptr_next)->status != FREE ){


	  ((struct segment_header *)search_seg->ptr_prev)->ptr_next = search_seg->ptr_next;
	  ((struct segment_header *)search_seg->ptr_next)->ptr_prev = search_seg->ptr_prev;
	  
	  //devalidate
	  search_seg->ptr_prev = NULL;
	  search_seg->ptr_next = NULL;
	  search_seg->status = FREE;

	  return 0;

	}

	//only next neighbor is free
	if( ((struct segment_header *)search_seg->ptr_prev)->status != FREE && ((struct segment_header *)search_seg->ptr_next)->status == FREE ){
	
	  search_seg->ptr_next = ((struct segment_header *)search_seg->ptr_next)->ptr_next;
	  
	  //Remark: watch out, there is no header at heap_upper
	  if( ((struct segment_header *)search_seg->ptr_next)->ptr_next != heap_upper)
	    ((struct segment_header *)((struct segment_header *)search_seg->ptr_next)->ptr_next)->ptr_prev = search_seg;
  
	  //devalidate
	  ((struct segment_header *)search_seg->ptr_next)->ptr_prev == NULL;
	  ((struct segment_header *)search_seg->ptr_next)->ptr_next == NULL;
	  ((struct segment_header *)search_seg->ptr_next)->status == FREE;

	  return 0;

	}
		

      }

	  
    }else
      
      //Are there more segments to check?
      printf("search_seg %u\n", (unsigned int) search_seg);
      if(search_seg->ptr_next != heap_upper){
	
	search_seg = search_seg->ptr_next;
	continue;
	
      }else{
	
	printf("the segment to be freed was not found\n");
	return -1;
	
      }

    
  }
}

void debug_print_headerloc(){

  struct segment_header * search_seg = (struct segment_header *) heap_lower;
  int nfirst = 0;

  while(1)
    {
      
      if((search_seg == heap_upper && nfirst) || search_seg == NULL)
	break;
      else{
	printf("header loc: %u ptr_prev: %u ptr_next %u\n", (unsigned int) search_seg, (unsigned int) search_seg->ptr_prev, (unsigned int) search_seg->ptr_next);	
	search_seg = search_seg->ptr_next;
      }

      nfirst = 1;
    }

}


int main(int argc, char* argv){

  //this symbolizes the memory we want to manage, not necessay in PORNOS
  heap_lower = malloc(num_bytes);
  heap_upper = heap_lower+num_bytes;

  //init start_segment, PORNOS would do this on (early) boot.
  ((struct segment_header *) heap_lower)->ptr_prev = heap_upper; // cyclic linked list
  ((struct segment_header *) heap_lower)->ptr_next = heap_upper; 
  ((struct segment_header *) heap_lower)->status = FREE;
  

  printf("header size: %d\n", sizeof(struct segment_header));
  printf("heap_lower: %u\n", (unsigned int) heap_lower);
  printf("heap_upper: %u\n\n", (unsigned int) heap_upper);

  void * p1;
  void * p2;
  void * p3;
  void * p4;
  void * p5;
  
  p1 = porn_malloc(512*1024);
  p2 = porn_malloc(512*1024);
  p3 = porn_malloc(512*1024);
  p4 = porn_malloc(512*1024);
  p5 = porn_malloc(100);

  printf("p1 allocated 512 kbytes @ %u\n", (unsigned int) p1);
  printf("p2 allocated 512 kbytes @ %u\n", (unsigned int) p2);
  printf("p3 allocated 512 kbytes @ %u\n", (unsigned int) p3);
  printf("p4 allocated 512 kbytes @ %u\n", (unsigned int) p4);
  printf("p5 allocated 100 bytes @ %u\n\n",  (unsigned int) p5);

  debug_print_headerloc();
  printf("freeing p1, %d\n", porn_free(p1));
  debug_print_headerloc();
  printf("freeing p2, %d\n", porn_free(p2));
  debug_print_headerloc();
  printf("freeing p3, %d\n", porn_free(p3));
  debug_print_headerloc();
  printf("freeing p4, %d\n", porn_free(p4));
  debug_print_headerloc();
  printf("freeing p5, %d\n", porn_free(p5));

  return 0;

}
